1. 题目描述(中等难度)

[warning] 46. 全排列

2. 解法一:回溯

class Solution {
    List<List<Integer>> resp = new ArrayList<>();
    List<Integer> ans = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
     if(null == nums || nums.length == 0){
         return resp;
     }
     backTracking(nums);
     return resp;
    }
    public void backTracking(int[] nums){
        //终止条件
        if(ans.size() == nums.length){
            resp.add(new ArrayList<>(ans));
            return;
        }
        //处理数据
        for(int i=0;i<nums.length;i++){
            if(ans.contains(nums[i])){
                continue;
            }
            ans.add(nums[i]);
            //递归
            backTracking(nums);
            //回溯
            ans.remove(ans.size()-1);
        }

    }
}

优化上面代码,使用一个used 数组来保存访问过的元素,回溯记得标记为false

class Solution {
    List<List<Integer>> resp = new ArrayList<>();
    List<Integer> ans = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
     if(null == nums || nums.length == 0){
         return resp;
     }
     used = new boolean[nums.length];
     backTracking(nums);
     return resp;
    }
    public void backTracking(int[] nums){

        if(ans.size() == nums.length){
            resp.add(new ArrayList<>(ans));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i] == true){
                continue;
            }
            used[i] = true;
            ans.add(nums[i]);
            //递归
            backTracking(nums);
            //回溯
            ans.remove(ans.size()-1);
            used[i] = false;
        }
    }
}
© gaohueric all right reserved,powered by Gitbook文件修订时间: 2021-12-08 23:22:22

results matching ""

    No results matching ""